Privatezza e Protezione dei Dati:

Privatezza e
Protezione dei Dati
Appunti di Maurizio Fortunati
Università degli Studi di Milano
Facoltà di Scienze e Tecnologie
Corso di Laurea Magistrale in Sicurezza informatica (Classe LM-66)
Esame di Privatezza e Protezione dei Dati
Docente: Samarati Pierangela
Anno accademico - 2018/2019Appunti di Privatezza e 
protezione dei dati 
Università degli Studi di Milano – Corso Magistrale in Sicurezza Informatica LM-66 
Corso tenuto da Pierangela Samarati [mail] 
AA 2018/19 
Sito Docente 
Link Ariel - Lucidi 
Link Ariel - Video lezioni 
V2.4 – Gennaio 2020 
Sommario 
1. Privacy and data protection in emerging scenarios ............................................................................................... 4 
Privacy nella pubblicazione dati ..................................................................................................................................... 4 
Rilascio di statistiche............................................................................................................................................. 4 
Tipologie di disclosure – 12/142 ........................................................................................................................... 4 
Restricted data and restricted access – 16/142 ................................................................................................... 5 
The anonimity problem -20/142 .......................................................................................................................... 6 
K-anonimity - 29/142 ...................................................................................................................................................... 6 
K-anonimity .......................................................................................................................................................... 6 
Generalized table with suppression – 32/142 ...................................................................................................... 8 
k-minimal generalization with suppression – 39/142 .......................................................................................... 8 
Computing a preferred generalization – 42/142 .................................................................................................. 9 
Classificazione di tecniche di k-anonimity – 43/142 ............................................................................................. 9 
Algorithms for computing a k-anonymous table – 49/142 ........................................................................................... 10 
Intro .................................................................................................................................................................... 10 
Algorithms  for AG_TS e AG_ - AG– 50/142 ........................................................................................................ 10 
Algorithms for _CS and CG_ - 62/142 ................................................................................................................. 11 
Attribute disclosure – 70/142 ....................................................................................................................................... 12 
intro .................................................................................................................................................................... 12 
ℓ-diversity – 74/142 ............................................................................................................................................ 12 
Skewness attack (attacco per asimmetria) – 76/142.......................................................................................... 13 
Similarity attack - 77/142 ................................................................................................................................... 13 
Group closeness (t-closeness) – 78/142 ............................................................................................................. 13 
External knowledge – 79/142 ............................................................................................................................. 13 
Multiple/longitudinal releases (rilasci multipli o longitudinali) – 86/142 .......................................................... 14 
m-invariance - 89/142 ........................................................................................................................................ 14 
Extended scenarios - 90/142 .............................................................................................................................. 14 
Differential privacy - 112/142 ............................................................................................................................. 15 
Sensitive value distributions – 119/142 ........................................................................................................................ 16 
Sensitive value distributions ............................................................................................................................... 16 
Privacy and genomic data - 125/142 .................................................................................................................. 16 
2. Macrodata and Microdata Protection ................................................................................................................. 17 
Microdata e Macrodata ................................................................................................................................................ 17 
Statistical data dissemination ............................................................................................................................. 17 
Macrodata Disclosure Protection Techniques – 3/66................................................................................................... 17 
Intro .................................................................................................................................................................... 17 
Protezione delle tabelle di conteggio e frequenza - 5/66 .................................................................................. 17 
Protection of tables of magnitude data - 29/66 ................................................................................................. 19 
Microdata Disclosure Protection Techniques – 43/66 ................................................................................................. 20 
Intro .................................................................................................................................................................... 20 
Microdata Disclosure Protection Techniques: - 51/66 ....................................................................................... 20 
3. Privacy in data Outsourcing ................................................................................................................................ 22 
Cloud computing ........................................................................................................................................................... 22 
Intro .................................................................................................................................................................... 22 
Characterization of Data Protection Challenges – 14/32 ............................................................................................. 22 
Security properties ............................................................................................................................................. 22 
Access requirements .......................................................................................................................................... 23 
Architectures ...................................................................................................................................................... 23 
4. Privacy of user ................................................................................................................................................... 24 
Privacy of users’ identities ............................................................................................................................................ 24 
Intro .................................................................................................................................................................... 24 
User empowerment - 4/51 ................................................................................................................................. 24 
Existing/emerging technologies supporting ABAC – 8/51 .................................................................................. 25 
User privacy preferences – 9/51 ......................................................................................................................... 25 
Some approaches – 12/51 ............................................................................................................................................ 26 
Cost-Sensitive Trust Negotiation – 13/51 ........................................................................................................... 26 
Point-based Trust Management Model – 17/51 ................................................................................................ 26 
Logic-based Minimal Credential Disclosure – 23/51 .......................................................................................... 27 
Privacy Preferences in Credential-based Interactions – 30/51........................................................................... 28 
5. Privacy and integrity of cloud data storage ......................................................................................................... 32 
Encryption ..................................................................................................................................................................... 32 
Intro .................................................................................................................................................................... 32 
Index – 7/270 ...................................................................................................................................................... 34 
Searchable encryption – 32/270 ......................................................................................................................... 36 
Inference exposure – 35/270 ............................................................................................................................. 37 
Bloom Filter – 50/270 ......................................................................................................................................... 38 
Data Integrity - 54/270 ....................................................................................................................................... 39 
Controllo dell’accesso - 57/270 .......................................................................................................................... 39 
Fragmentation – 126/270 ............................................................................................................................................. 49 
Intro .................................................................................................................................................................... 49 
Non-communicating pair of servers - 131/270 ................................................................................................... 50 
Multiple non-linkable fragments – 140/270 ....................................................................................................... 53 
Keep a few – 151/270 ......................................................................................................................................... 57 
Publishing Obfuscated Associations 180/270 ............................................................................................................... 63 
Intro .................................................................................................................................................................... 63 
Anonymizing Bipartite Graph 182/270 ............................................................................................................... 64 
Fragments and Loose Associations 189/270 ...................................................................................................... 66 
6. Privacy delle query ............................................................................................................................................. 75 
Confidenzialità delle query ........................................................................................................................................... 75 
intro .................................................................................................................................................................... 75 
Path ORAM ......................................................................................................................................................... 75 
Shuffle index ....................................................................................................................................................... 77 
7. Domande e risposte ........................................................................................................................................... 81 
Capitolo 1 - Privacy and data protection in emerging scenarios .................................................................................. 81 
Capitolo 2 - Macrodata and Microdata Protection ....................................................................................................... 81 
Capitolo 3 - Privacy in data Outsourcing ....................................................................................................................... 81 
Capitolo 4 - Privacy of user ........................................................................................................................................... 81 
Cost-sensitive trust negotiation.......................................................................................................................... 81 
Point Based trust management model ............................................................................................................... 82 
Logic based minimal credential disclosure ......................................................................................................... 82 
Privacy preferences in credential-based interactions ........................................................................................ 83 
Capitolo 5 -Privacy and integrity of cloud data storag.................................................................................................. 85 
Encryption ........................................................................................................................................................... 85 
Inference expsoure ............................................................................................................................................. 87 
Fragmentation .................................................................................................................................................... 87 
Ottimizzazioni ..................................................................................................................................................... 90 
Pubblicazione associazioni dei dati ..................................................................................................................... 91 
Selective Encryption and Over-Encryption – Controllo dell’accesso .................................................................. 93 
Capitolo 6 - Privacy delle query .................................................................................................................................... 95 
Path Oram ........................................................................................................................................................... 95 
Shuffle index ....................................................................................................................................................... 95 
8. Indice delle figure .............................................................................................................................................. 97 
 
  
1. Privacy and data protection in emerging scenarios 
Privacy nella pubblicazione dati 
Rilascio di statistiche  
Il rilascio di dati c’è sempre stato e sempre ci sarà, all’inizio avveniva in forma statistica.  
Per esempio un ospedale rilascia statistiche sui propri pazienti.  
Esistono due metodi per recuperare le informazioni: 
• DBMS statistico: Processo dinamico per cui io posso chiedere ciò che voglio purché non si riferisca a 
singoli individui ma ad aggregazioni di individui. Proteggere la privacy in questo caso è più semplice 
perché vengono trattate query aggregate. Non risponde se la quantità di dati è troppo piccola o 
troppo grande. Due problemi:  
1. Non posso mostrare troppi dati a un utente in un arco temporale troppo piccolo perché 
accumula troppa conoscenza. Cosa considero come arco temporale? Due query consecutive 
possono essere significative ma una ieri e una oggi? 
2. Cosa considero come soggetto accumulante conoscenza? Considero la singola login? Due 
utenti con due login differenti potrebbero parlarsi. 
• Statistical data: vengono rilasciati tutti i dati in maniera statistica. 
 
Nel passato i dati venivano rilasciati in macrodata (sostanzialmente dati aggregati). Oggi invece si spinge 
sempre di più verso i microdata (dati più mirati, più specifici). Nel caso dei microdata si è più esposti a rischi di 
privacy e in particolare ai linking attacks.  
 
Macrodata: dati in forma aggregata o statistiche, spesso senza gli identificativi dei singoli soggetti. 
 
Microdata: si parla di micro data quando i dati rilasciati non sono informazioni in forma aggregata 
(statistiche), ma sono dati veri e propri del mio database (dati grezzi). 
 
I Macrodata, si possono dividere in due gruppi: 
• Tabelle di conteggio/frequenza: dati aggregati computati, il contenuto della tabella è un conteggio (o 
percentuale) degli individui che soddisfano un certo requisito 
• Magnitude (importanza) data: Un’ aggregazione su un certo dato di interesse. Per esempio il valore 
medio dello stipendio. 
 
Tipologie di disclosure 
1. Identity disclosure: è possibile identificare un individuo dai dati. Il fatto che l’individuo faccia parte di un 
certo tipo di dati può dare fastidio. 
2. Attribute disclosure: (trattato più avanti) dati sensibili di un individuo sono rivelati dai dati. 
3. Inferential disclosure: Chiamati anche linking, sono quelle informazioni ricavate attraverso le correlazioni 
fra diversi fonti.  
Tipologie di disclosure – 12/142 
Identity disclosure 
Utilizzando i macrodata è difficile che esistano possibilità di identity disclosure, in quanto i dati rilasciati sono 
dati aggregati e a meno che non ci sia carenza di dati e quindi si possa risalire a uno specifico individuo.  
Vedi Figura 1 oppure la slide 9, nel caso in cui County D è composta da due soli elementi dove entrambi 
hanno i valori pari a 40-59.  
Se ci fosse una sola persona e l’attaccante Mallory (M) è a conoscenza di chi sia la persona che è presente 
nella tabella allora può determinare facilmente i benefit. 
Nei microdata se riesco a identificare che un individuo è all’interno di un dataset e che una certa tupla 
appartiene a lui allora si incorre in grossi problemi. 
 
Figura 1: Macrodata Count example 
Attribute disclosure 
Avviene quando informazioni confidenziali si possono attribuire in modo certo o parziali nei confronti di una 
persona. Queste informazioni confidenziali permettono di identificare il soggetto con:  
• Certezza assoluta  
• Ad un livello abbastanza alto di certezza per cui ci si può considerare esposti 
 
Inferential disclosure 
Riuscire ad ottenere informazioni riservate attraverso correlazioni. 
Conoscendo che un individuo fa parte di un dataset con determinate malattie. E vedo che alcune malattie 
sono tipicamente da bambino e alcune sono tipicamente da adulto. Una malattia viene tipicamente ad adulti 
che fanno il lavoro dell’individuo che conosco. A questo punto posso dire con abbastanza sicurezza che 
l’individuo che conosco abbia quella malattia. 
 
Restricted data and restricted access – 16/142 
Intro 
Come proteggere i dati se li devo rilasciare? 
In un primo step rimuovo gli identificatori espliciti dell’identità (nome, cognome, email, telefono ecc…), 
ottenendo quello che viene chiamato dato anonimizzato.  
 
Tecniche di protezione per conteggio/frequenza macrodata 
I dati collezionati sono pubblicati in tabelle che mostrano counts o frequencies. 
Le tecniche per proteggere questo genere di dati sono: 
• Sampling (campionatura, calcolare su un campione rappresentativo): pubblicare un 
sondaggio/panoramica invece di un censimento specifico. 
• Regole speciali: definire restrizioni sul livello di dettaglio delle informazioni che fornisco.  
Ad esempio: pubblico gli stipendi con delle soglie 5 -10 -15 -20 
• Threshold rules (regole di soglia): regole che definiscono i casi in cui eliminare/sopprimere dati perché 
si riferiscono a un gruppo molto ristretto di individui e quindi possono diventare sensibili. 
 
Tecniche di protezione per microdata 
Le tecniche per proteggere questo genere di dati sono: 
• Masking techniques: inserire del “rumore” all’interno dei dati quindi, di fatto, andando a modificare i 
dati. Questo genere di tecniche può attuarle solo chi rilascia i dati, perché deve stare attento a falsare i 
dati in maniera mirata; se vengono modificati  troppo o in maniera erronea potrebbe invalidare tutta la 
statistica. 
1. Non perturbative: i dati originali non sono modificati ma alcuni dati vengono soppressi o alcuni 
dettagli rimossi, per esempio: generalizzazione (i dati vengono presi a fasce voti [24-27], [28-30], 
campionamento (prendo solo un sottoinsieme), soppressione di alcuni valori (invece di 10 esami 
prendi solo 7 esami di uno studente)] . 
2. Perturbative: i dati originali vengono modificati (arrotondo i valori, scambio i valori da un
individuo all’altro).
• Synthetic data generation techniques: rilasciare dati verosimili invece dei dati reali
1. Fully Synthetic: tutti i dati sono sintetici
2. Partially Synthetic: il dataset rilasciato contiene un mix di dati sintetici e non.
The anonimity problem -20/142 
Intro 
I dati che rilascio io non sono gli unici. Esistono molti altri dati che vengono rilasciati da altri enti/persone per 
cui è possibile fare degli incroci fra i dati (Inferential disclosure). Questo tipo di attacchi vengono chiamati 
linking attacks quindi un dato che prima era stato de-identificato (cioè tolte informazioni importanti) può 
essere re-identificato. Vedi slide 21. 
Classificazione degli attributi nei microdata 
Gli attributi possono essere classificati in: 
• Identificatori: identificano unicamente una persona (per esempio codice fiscale).
• Quasi-identificatori: attributi che combinati possono identificare una persona.
• Confidenziali: attributi che contengono dati sensibili.
• Non confidenziali: attributi che non contengono dati sensibili e la cui release non causa disclosure.
Fattori che contribuiscono ad aumentare il rischio di disclosure 
1. Esistenza di record di alta visibilità (per esempio lavori molto particolari (papa, presidente della
repubblica), o redditi molto alti.
2. Possibilità di fare matching fra i microdata e informazioni esterne (individui che hanno una
combinazione di informazioni unica o molto particolare).
La possibilità di linking aumenta se: 
• Ci sono tanti attributi in comune fra i microdata e le risorse esterne.
• Accuratezza/precisione dei dati.
• Più sorgenti hai, più capacità di linking hai.
Fattori che contribuiscono a ridurre il rischio di disclosure 
1. Una tabella di microdata contiene solo una parte della popolazione (se una persona cerca un individuo
specifico può darsi che non sia presente in tabella).
2. L’informazione specificata nei microdata table non è più aggiornata e quindi ha una percentuale di
errore.
Misure di rischio 
Bisogna calibrare fra proteggere i dati e renderli utilizzabili. Magari li proteggo benissimo ma non posso più 
ottenere informazioni utili ai fini dei miei obbiettivi. 
K-anonimity - 29/142
K-anonimity
Non si può dare garanzia di privacy assoluta ma solo un certo livello di incertezza.
K-anonimity: nei dati che rilasciati si garantisce che ciascuna tupla sia mappabile indistintamente su almeno k
elementi.
Nell’esempio della slide 21, se consideriamo una 4-anonimity, oltre che a Sue Doe ci saranno almeno altre tre
persone con quelle stesse caratteristiche.
Quasi-identifier: insieme degli attributi che possono essere sfruttati per il linking attack. 
L’insieme delle tuple che potrebbero ricondurre alla persona vengono denominate quasi identifier.  
In K anonimity  si definisce che ogni tupla del quasi-identifier debba apparire almeno k-volte. 
Per attuare questa k-anonimity possiamo utilizzare le tecniche di protezione trattate precedentemente. 
In particolare possiamo utilizzarne due (non sporcano i dati): 
• Generalization: non pubblicare informazioni specifiche ma generalizzare (invece di pubblicare l’anno, il 
mese e il giorno di nascita, pubblicare solo l’anno. In questo modo la capacità di linking cala 
drasticamente, oppure come il cap, che si utilizza quello generico, es milano 20100). 
• Suppression: soppressione di alcuni dati. 
 
In questo modo il quasi-identifier non punta più ad una sola persona ma a più persone. 
 
 
Figura 2: Slide 33 
 
Se tu hai una tupla che prende valori da un certo dominio, se ciascuno di questi domini ha una gerarchia 
sopra, hai anche tutte le possibili combinazioni della gerarchia, tutti i possibili prodotti cartesiani. 
 
 
Figura 3: slide 34 
 
Gerarchia dei valori 
Mi dice quali valori vengono generalizzati a quali valori del dominio sulla generalizzazione. 
Per esempio asiatico, nero e bianco sono tutte -> persone (vedi slide 36).  
Una gerarchia è un albero perché ogni nodo ha uno e un solo padre e la radice non ha padre. 
 
Generalized table with suppression – 32/142 
 
Date due tabelle Ti e Tj definite sullo stesso insieme di attributi diremo che Tj è una generalizzazione (con 
tuple soppresse) di Ti ( viene scritta così ) se:  
 
Supponendo di applicare la soppressione al livello della tupla, se ho un singolo attributo che voglio eliminare, 
vado a eliminare l’intera tupla. Ho generalizzato la razza, ma ho lasciato lo zip code specifico eliminando le 
tuple con valori univoci. GT è una generalizzazione di PT 
 
CIASCUN CLUSTER DI RISPONDENTI E’ ALMENO DI K = 2        (ci sono due categorie di rispondenti: blu e rossi) 
 
Più è alto K più è bassa la specificità dei dati 
 
• |Tj| ≤ |Ti| ----> La cardinalità di Tj è minore o al 
più uguale alla cardinalità di Ti 
• Il dominio  dom(A,Tj) di ogni attributo A in Tj è 
uguale, o è una generalizzazione, del dominio 
dom(A,Ti) dell’attributo A in Ti (the domain 
dom(A,Tj) of each attribute A in Tj is equal to, or a 
• generalization of, the domain dom(A,Ti) of 
attribute A in Ti) 
• Per ciascuna tupla di Tj esiste una tupla 
corrispondente in Ti (non è sempre vero il 
contrario) It is possible to define an injective 
function associating each tuple tj in Tj with a tuple 
ti in Ti, such that the value of each attribute in tj is 
equal to, or a generalization of, the value of the  
corresponding attribute in ti. 
 
k-minimal generalization with suppression – 39/142 
Distance vector: Nella ricerca di una soluzione di generalizzazione è necessario avere la protezione richiesta 
ma non ridurre l’utilità dei dati (è quindi utile stabilire una soglia di soppressione). 
Quindi la tabella che preferiremo pubblicare è quella, si generalizzata, ma che rilascia il maggior numero di 
informazioni. 
 
Figura 5: Distance vector 
 
Ti è una generazione minimale di Tj quando: 
• Quando soddisfa la soglia di soppressione (Stabilita in partenza) 
Figura 4: Generalizzazione con soppressione 
• Quando la nostra tabella (Ti) ha più tuple di ogni altra tabella Tz che ha sempre lo stesso vettore di 
distanza. 
• Quando non esiste alcun’altra tabella che soddisfa le precedenti condizioni con un vettore di distanza 
minore della mia (Ti)  
 
Date due tabelle Ti e Tj tali che Ti <= Tj e dato MaxSup la massima soglia accettata di soppressione di tuple. Tj 
viene detta k-minimal generalization di Ti se: 
Tj satisfies k-anonymity enforcing minimal required suppression, that is, Tj satisfies k-anonymity and ∀Tz : Ti 
<=Tz,DVi,z = DVi,j, Tz satisfies k-anonymity ⇒|Tj| ≥ |Tz| 
 
(Soddisfa k-anonimity sopprimendo il minimo insieme di tuple necessarie per soddisfare k-anonimity a quel 
livello di generalizzazione) (si legge: se Tj soddisfa k-anonimity e per ogni Tz tale che Tz domina Ti e il distance 
vector DVi,z = DVi,j e Tz soddisfa k-anonimity => Tj ha più tuple di Tz) 
(in sostanza: qualsiasi altra generalizzazione (tabella generalizzata) che generalizza lo stesso di me sopprime 
più di me quindi sono meglio io che sopprimo di meno). 
 
|Ti|−|Tj| ≤ MaxSup (Non sopprime più tuple della condizione che gli ho dato) 
∀Tz : Ti <=Tz and Tz satisfies conditions 1 and 2 ⇒¬(DVi,z < DVi,j)  
(Qualsiasi altra tabella che soddisfa le prime due condizioni non è mio discendente in gerarchia. (Non ha 
distance vector più piccolo del mio))(cioè se un’altra tabella generalizza meglio di me ⇒¬(DVi,z < DVi,j)).  
 
Computing a preferred generalization – 42/142 
I criteri per scegliere la generalizzazione minima sono: 
• Minima distanza assoluta: Prendo la soluzione che fa meno passi di generalizzazione in totale. è 
preferibile sempre la minore distanza assoluta ovvero il minore numero di step. 
• Minima distanza relativa: la distanza relativa è una distanza pesata. Cioè divide ciascun passo per 
l’altezza della gerarchia. L’altezza della razza per esempio è 1 (asian->person) mentre l’altezza dello zip è 
2 (94141->9414*->941**, 94131->9413*->941**, vedi slide 36).  
Per cui considerare la minima distanza vuol dire che se generalizzo la razza -> 1(passo)/1(altezza)=1 
mentre se generalizzo lo zip -> 1(passo)/2(altezza)=1/2=0.5 
• Distribuzione massima: preferire la generalizzazione con il maggior numero di tuple distinte 
• Minima soppressione: preferire la generalizzazione che sopprime meno tuple 
 
Classificazione di tecniche di k-anonimity – 43/142 
Generalizzazioni e soppressioni possono essere applicate con differenti livelli di granularità: 
• Generalizzazione: si può applicare a tutta la colonna o anche alle singole celle (se sono in un ospedale in 
cina e ci sono 995 asiatici e gli altri 5 sono un’italiano, un francese, un tedesco, un russo e uno spagnolo 
posso generalizzare in “asiatico”, “resto del mondo”) 
• Soppressione: si può applicare a una 
riga, una colonna o una singola cella 
 
 
PT tabella di partenza 
 
Esempio AG_TS: questa soluzione generalizza a 
livello attributo e sopprime a livello di tupla 
 
 
 Figura 6:Tabella AG_TS 
Figura 8: Tabella CG&TS 
Figura 9: Tabella AS_&CS 
 
Esempio AG_CS: questa soluzione generalizza a 
livello attributo (le colonne sono tutte 
omogenee) e sopprime a livello di cella. 
 
Esempio AG_: generalizza a livello attributo e 
non ho soppressione. 
 
 
 
 
 
 
Esempio CG_: Generalizzazione a livello di cella 
(da i dati più specifici e sopprime il meno 
possibile ma la tabella non è più omogenea). 
 
Esempio _TS: Applico la soppressione a livello 
tupla (non posso rilasciare niente). 
 
 
 
 
 
 
Esempio _AS: Applico la soppressione a livello 
attributo 
Esempio _CS: Applico la soppressione a livello di 
cella (non generalizzo niente e rilascio solo le 
informazioni) 
 
 
 
 
 
 
Algorithms for computing a k-anonymous table – 49/142 
Intro 
Problema computazionalmente difficile, perché per trovare la tabella migliore dovrei provarle tutte. 
 
Algorithms  for AG_TS e AG_ - AG– 50/142 
 
Generalizzazione Attributi / TS = Soppressione tupla 
 
Computing a k-minimal solution 
Generalizzazione localmente minima: la minima generalizzazione che permette k-anonimity in un ramo 
dell’albero formato da tutte le possibili generalizzazioni.  
Una generalizzazione localmente minima può non essere la generalizzazione minima globale ma il contrario si 
ovviamente. 
 
Figura 7:Tabella AG_CS 
 
 
Ammettendo che R1,Z1 è la generalizzazione localmente minima in quel ramo non è detto che lo sia 
globalmente perché R0,Z1 potrebbe soddisfare la k-anonimity desiderata (Vedi slide 39). 
Si può utilizzare un algoritmo che utilizza una ricerca binaria. Si taglia l’albero a metà h/2: 
• Se esiste una soluzione che soddisfa k-anonimity allora taglia ulteriormente a metà h/4 
• Se non esiste cerca in 3h/4 
To reduce the computational cost, it adopts a distance vector matrix that avoids the explicit computation of 
each generalized table. 
Vedi slide 53-54 per degli esempi. 
Potrebbe però essere che la gerarchia NON è un albero quindi un algoritmo di ricerca binaria si rivelerebbe 
completamente scorretto! Se generalizzo per anni per esempio e faccio una generalizzazione prima per 10 
anni e poi per 25 non ho più un albero. 
 
k-Optimize algorithm 
Viene definito un nuovo sistema per generalizzare i valori. Il sistema in questo caso è generalizzare valori che 
sono adiacenti. 
Ad esempio assumendo di avere i domini di generalizzazione in sequenza (all’interno di ciascun dominio di 
generalizzazione è come se i valori fossero ordinati), invece di rappresentare con asterischi (Es. 92410, 92411 
→ 9241*) vado a clusterizzare (raggruppare) i valori adiacenti 
In razza non è possibile ottenere una soluzione più specifica quindi creo un cluster generalizzato 
In zip, (essendo che 9413 è guale per le prime due coppie e 9414 è uguale per le seconde) posso creare due 
gruppi. 
 
                 Race                                                   ZIP 
{[asian] [black] [white]}       {[94138] [94139] [94141] [94142]} 
      1           2            3                     4             5            6             7 
• corresponds to: 
o Race: {1}, that is: [asian or black or white] 
o ZIP: {4, 6}, that is: {[94138 or 94139],[94141 or 94142]} 
 
Organizzo lo spazio di tutte le possibili soluzioni e costruisco un albero.  
Per esempio per lo ZIP la foglia più bassa corrisponde a 4 gruppetti differenti (4|5|6|7). La radice corrisponde 
a un gruppo che contiene tutti (4 5 6 7). L’algoritmo consiste nel partire dalla radice e vedere se le foglie 
soddisfano le condizioni. Se non le soddisfano posso tagliare direttamente tutto il ramo. 
 
Algorithms for _CS and CG_ - 62/142 
Mondrian multidimensional algorithm  
Ci sono almeno due ragioni perché è meglio generalizzare a livello di attributo piuttosto che a livello di cella. 
La prima ragione è una ragione di efficienza perché le combinazioni di celle sono molte di più. 
La seconda ragione è l’omogeneità dei dati. Per esempio nella slide 47 i dati sono poco omogenei poiché le 
date sono tutte diverse. Vedi slide 65. Ogni dimensione per ogni attributo. 
Mondrian algorithm is flexible and can operate 
• On a different number of attributes 
o single-dimension 
o multi-dimension 
• with different recoding (generalization) strategies  
o global recoding (generalizzazione a livello di colonna) 
o local recoding (generalizzazione a livello di cella) 
Figura 10:Esempio generalizzazione 
• with different partitioning strategies (diverse strategie per il taglio del piano. Per esempio nella slide 65 
le aree erano disgiunte ma potrebbero essere sovrapposte) 
o strict (i.e., non-overlapping) partitioning 
o relaxed (i.e., potentially overlapping) partitioning 
• Using different metrics to determine how to split on each dimension 
 
Approximation algorithms 
Esistono anche degli algoritmi di approssimazione. 
 
k-anonimity revisited 
Vedi slide 69. La tabella revisited mantiene k-anonimity! Le due sotto invece no! 
 
 
Figura 11: 2 anonymity slide 69 
 
Attribute disclosure – 70/142  
intro 
k-anonymity è vulnerabile ad alcuni tipi di attacchi. Perché il suo scopo è quello di proteggere/confondere 
l’identità associata ad un record. Il problema è vedere poi le informazioni sensibili e i problemi di correlazione 
tra i vari dati. 
 
Per esempio nella tabella la k-anonimity è soddisfatta ma le 
due persone in arancione e in rosso hanno la stessa malattia 
per cui chiunque delle due io sia gli altri sapranno che ho 
quella malattia.  
Questo problema viene detto problema di homogeneity. 
  
Un altro problema è quello di background knowledge.  
Ovvero basandomi sulle mie personali conoscenze sulla 
persona riesco a risalire a quale delle due è in tabella. Se 
conosco che Mr.X tutte le mattine corre sicuramente non 
soffre di fiato corto, per cui posso dedurre che soffra di 
un’altra patologia. 
 
ℓ-diversity – 74/142 
Oltre ad utilizzare k-anonimity bisogna differenziare i dati sensibili.  
Continuando con l’esempio delle malattie, bisogna avere almeno L valori diversi, in modo tale da contrastare i 
problemi di homogeneity. 
Se Hellen è una donna bianca ed è una maratoneta, difficilmente sarà obesa o avrà il fiato corto oppure 
malata di cuore; di conseguenza si può dedurre che hellen abbia il cancro.  
Figura 12: tabella di esempio 
Avendo una tabella k-anonimizzata devo differenziare i dati sensibili. La tabella si può considerare L diverse 
quando contiene almeno L valori diversi dello stesso dato sensibile. 
(Quindi servono cluster di dimensione k con almeno L diversi valori.) 
 
La l diveristy rende più difficile anche un attacco di tipo background knowledge 
 
  
 
 
 
 
 
 
 
 
 
Skewness attack (attacco per asimmetria) – 76/142 
L-diversity lascia spazio ad attacchi basati sulla distribuzione dei valori all'interno dei cluster. 
Lo “ Skewness Attack” avviene quando la distribuzione in un cluster è differente dalla distribuzione della 
popolazione reale. 
 
Se avessi una tabella in cui è soddisfatta k-
anonimity e ℓ-diversity con 4 record di cui 3 con la 
stessa malattia, vuol dire che il 75% di coloro che 
sono in quella tabella hanno quella malattia posso 
determinare con una certa sicurezza la malattia di 
una persona. 
 
 
Similarity attack - 77/142 
L’attacco di similarità è quando pur essendoci differenze nel nome di attributo, il loro significati sono simili. 
per esempio ulcera e gastrite, sono due malattie differenti ma non abbastanza per determinare una grande 
distinzione dal farmi percepire che tipologia di malattia abbia una persona. 
  
Group closeness (t-closeness) – 78/142 
Dopo aver eseguito k-anonimity, l-diversity, bisogna controllare che i gruppetti abbiano una distribuzione 
simile a quella reale. Ad esempio evitando i picchi o blocchi di persone con le stesse  malattie, ad esempio 
inserendo una persona in un gruppo dove il 75% ha il diabete, quando nella realtà solo il 20% della 
popolazione ne soffre. 
Questo in realtà invalida i dati perché di fatto l’utilità cala drasticamente, in quanto modifico la distribuzione 
verso quello che è il dato di pubblico dominio. 
 
External knowledge – 79/142 
The consideration of the adversary’s background or external knowledge is necessary when reasoning about 
privacy in data publishing. 
RACE DOB SEX ZIP DISEASE 
Asian 64  F  941**  hypertension 
asian  64  F  941** obesity 
asian  64  F 941**  chest pain 
asian  63  M 941**  obesity 
black  63  M 941** obesity 
black  64 F 941** short breath 
white  64 M 941** short breath 
white 64  F 941** heart patient 
white  64  F 941**  short breath 
white  64  F  941** Cancer 
white  64  F 941** obesity 
Figura 13: Skewness attack example table